package codeRandomThoughts.Test106从中序与后序遍历序列构造二叉树;

import codeRandomThoughts.utils.TreeNode;


//二刷 优化算法
public class Solution3 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTreeByIndex(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }

    //左闭右闭
    public TreeNode buildTreeByIndex(int[] inorder, int inorderBegin, int inorderEnd, int[] postorder, int postorderBegin, int postorderEnd) {
        //递归终止条件
        //数组为空说明遍历到了空结点
        if (inorderBegin > inorderEnd) {
            return null;
        }

        //后序遍历数组的最后一个元素是根节点
        int rootVal = postorder[postorderEnd];
        TreeNode root = new TreeNode();
        root.val = rootVal;

        //找根节点在中序遍历数组中的位置
        int rootIndex = 0;
        for (int i = inorderBegin; i <= inorderEnd; i++) {
            if (inorder[i] == rootVal) {
                rootIndex = i;
                break;
            }
        }

        //把原来的中序序列按左右子树进行划分
        int inorderLeftEnd = rootIndex - 1;
        int inorderRightBegin = rootIndex + 1;

        //把原来的后序序列按左右子树进行划分
        int postOrderLeftEnd = inorderLeftEnd - inorderBegin + postorderBegin;
        int postOrderRightBegin = postOrderLeftEnd + 1;
        int postOrderRightEnd = postorderEnd - 1;


        root.left = buildTreeByIndex(inorder, inorderBegin, inorderLeftEnd, postorder, postorderBegin, postOrderLeftEnd);
        root.right = buildTreeByIndex(inorder, inorderRightBegin, inorderEnd, postorder, postOrderRightBegin, postOrderRightEnd);
        return root;
    }
}
